package string;

/**
 * 28. 找出字符串中第一个匹配项的下标
 * KMP算法
 * 求出前缀表next数组
 *
 * @author Api
 * @date 2023/10/15 0:01
 */
public class Code28_SubscriptFirstMatchInString {
    // KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
    // 因为前缀表要求的就是相同前后缀的长度。
    // 所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等.....
    // 字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
    /*
        构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：
        初始化
        处理前后缀不相同的情况
        处理前后缀相同的情况
    */
    //=======================================================================================================
    public static void main(String[] args) {
        // "sadbutsad"
        int i = new Code28_SubscriptFirstMatchInString().strStr1("aabaabaafa", "aabaaf");
        System.out.println(i);
    }

    /**
     * 基于窗口滑动的算法
     * <p>
     * 时间复杂度：O(m*n)
     * 空间复杂度：O(1)
     * 注：n为haystack的长度，m为needle的长度
     */
    public int strStr(String haystack, String needle) {
        int m = needle.length();
        // 当needle是空字符串时，我们应当返回0
        if (m == 0) {
            return 0;
        }
        int n = haystack.length();
        if (n < m) {
            return -1;
        }
        int i = 0;
        int j = 0;
        while (i < n - m + 1) {
            // 找到首字母相等
            while (i < n && haystack.charAt(i) != needle.charAt(j)) {
                i++;
            }
            if (i == n) { // 没有首字母相等的
                return -1;
            }
            // 遍历后续字符，判断是否相等
            i++;
            j++;
            while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }
            if (j == m) {// 找到
                return i - j;
            } else {// 未找到
                i -= j - 1;
                j = 0;
            }
        }
        return -1;
    }

    //=======================================================================================================
    // KMP
    // 前缀表（不减一）Java实现
    public int strStr1(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) {
                j = next[j - 1];
            }
            if (needle.charAt(j) == haystack.charAt(i)) {
                j++;
            }
            if (j == needle.length()) {
                return i - needle.length() + 1;
            }
        }
        return -1;
    }
    // 前缀表
    private void getNext(int[] next, String s) {
        int j = 0; // 指向前缀末尾位置
        next[0] = 0;
        // i指向后缀末尾位置
        for (int i = 1; i < s.length(); i++) {
            // 前后缀不相同的情况
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = next[j - 1];
            }
            // 前后缀相同的情况
            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }
              next[i] = j;
        }
    }
}
